package com.lw.leetcode.dp.b;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * Created with IntelliJ IDEA.
 * 763. 划分字母区间
 *
 * @author liw
 * @version 1.0
 * @date 2021/11/1 13:56
 */
public class PartitionLabels {

    public static void main(String[] args) {
        PartitionLabels test = new PartitionLabels();
        String str = "ababcbacadefegdehijhklij";
        List<Integer> list = test.partitionLabels(str);
        System.out.println(list);
    }


    public List<Integer> partitionLabels(String s) {
        int[][] arr = new int[26][2];
        for (int[] ints : arr) {
            ints[0] = Integer.MAX_VALUE;
        }
        char[] chars = s.toCharArray();
        int length = chars.length;
        for (int i = 0; i < length; i++) {
            int[] ints = arr[chars[i] - 'a'];
            ints[0] = Math.min(ints[0], i);
            ints[1] = Math.max(ints[1], i);
        }
        Arrays.sort(arr, (a, b) -> a[0] - b[0]);
        List<Integer> list = new ArrayList<>();
        int max = arr[0][1];
        int last = -1;
        for (int[] ints : arr) {
            int a = ints[0];
            int b = ints[1];
            if (a == Integer.MAX_VALUE) {
                break;
            }
            if (a > max) {
                list.add(max - last);
                last = max;
            }
            max = Math.max(max, b);
        }
        list.add(max - last);
        return list;


    }

}
